package cz.cvut.fit.mi_paa.knapsack.strategy;

import cz.cvut.fit.mi_paa.abs.Context;

import java.io.FileWriter;
import java.io.IOException;

/**
 * Created with IntelliJ IDEA.
 * User: milos
 * Date: 16.11.12
 * Time: 11:35
 * To change this template use File | Settings | File Templates.
 */
public class DynamicProgrammingKnapsackStrategy extends KnapsackStrategy {
    private int itemCount, capacity;
    private boolean[][] sol;
    public DynamicProgrammingKnapsackStrategy(Context context) {
        super(context);
    }

    @Override
    public void solve() throws IOException {
        itemCount = instance.getItemNumber();
        capacity = instance.getCapacity();
        int[][] opt = new int[itemCount+1][capacity+1];
        sol = new boolean[itemCount+1][capacity+1];
        context.getSw().start();

        for (int n = 1; n <= itemCount; n++) {
            for (int w = 1; w <= capacity; w++) {

                int option1 = opt[n-1][w];

                int weightN = instance.getItems()[n-1].getWeight();
                int priceN = instance.getItems()[n-1].getPrice();
                int option2 = (weightN <= w) ? priceN + opt[n-1][w-weightN] :
                        Integer.MIN_VALUE;

                opt[n][w] = Math.max(option1, option2);
                sol[n][w] = (option2 > option1);
            }
        }
        context.getSw().stop();
    }

    @Override
    public void writeResult() throws IOException {
        boolean[] take = new boolean[itemCount +1];
        int priceSum=0;
        for (int n = itemCount, w = capacity; n > 0; n--) {
            if (sol[n][w]) {
                int weightN = instance.getItems()[n-1].getWeight();
                priceSum += instance.getItems()[n-1].getPrice();
                take[n] = true;  w = w - weightN;
            } else {
                take[n] = false;
            }
        }
        FileWriter resultWriter = context.getResultWriter();
        resultWriter.write(instance.getId() + " ");
        resultWriter.write(context.getSw().getTimeMillis() + " ");
        resultWriter.write(instance.getItemNumber() + " ");
        resultWriter.write(priceSum+ "  ");

        for (int i = 1; i<take.length;i++) {
            if(i!=(take.length-1))
                resultWriter.write(take[i]+" ");
            else
                resultWriter.write(take[i]+"\n");
        }
    }
}
